/**
 * 对红黑树的简单测试。代码复用了二叉树的测试代码。
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include <cds/rbtree.h>
#include "bintree_test_tools.h"
#include "test_tools.h"

/// 检查单个节点是否合法。合法返回0，非法返回1.
static int __rb_is_node_valid(struct rb_node *node)
{
    if (node == NULL || rb_parent(node) == node) {
        /// NULL节点或者空节点视为非法。
        printf("p0\n");
        return 1;
    }
    if (rb_parent(node) == NULL) {
        /// 父节点为NULL则说明该节点为最顶层的节点。
        if (!rb_is_node_black(node)) {
            /// 最顶层节点只允许为黑节点。
            printf("p1\n");
            return 1;
        }
    } else {
        if (rb_parent(node)->left != node && rb_parent(node)->right != node) {
            /// 当前节点没有与父节点相连接。
            printf("p2\n");
            return 1;
        }
    }

    if (node->left != NULL) {
        if (rb_parent(node->left) != node) {
            /// 左子节点存在，但并未与当前节点完全连接。
            printf("p3\n");
            return 1;
        }
    }

    if (node->right != NULL) {
        if (rb_parent(node->right) != node) {
            /// 右子节点存在，但并未与当前节点完全连接。
            printf("p4\n");
            return 1;
        }
    }

    /// 只需要单独测试红节点
    if (!rb_is_node_black(node)) {
        if (node->left == NULL && node->right == NULL) {
            /// 两个叶子节点都为NULL的红节点合法。
            return 0;
        }
        if (rb_is_node_black(node->left) && rb_is_node_black(node->right)) {
            /// 两个叶子节点都为非NULL黑节点时合法。
            if (node->left != NULL && node->right != NULL) {
                return 0;
            }
            /// 红节点要么只有两个NULL节点，要么只有两个非NULL黑节点。
            printf("p5\n");
            return 1;
        }
        /// 其他情况下不合法。
        printf("p6\n");
        return 1;
    }

    return 0;
}

/// 检查一个子树的黑平衡，如果平衡返回该子树的黑高，否则返回-1
static int __rb_check_black_balance(struct rb_node *node)
{
    if (node == NULL) {
        return 0;
    }
    int left_depth = __rb_check_black_balance(node->left);
    int right_depth = __rb_check_black_balance(node->right);
    if (left_depth < 0 || right_depth < 0) {
        /// 子树中发现了不平衡。
        return -1;
    }
    if (left_depth != right_depth) {
        /// 当前节点发现不平衡。
        return -1;
    }
    if (rb_is_node_black(node)) {
        return left_depth + 1;
    } else {
        return left_depth;
    }
}

#define __RB_DESPLAY_A_SINGLE_NODE(name, node)  do {    \
    if ((node) != NULL) {   \
        printf(name ": (%s), val: %d\n",    \
            rb_is_node_black((node)) ? "black" : "red",  \
            rb_entry((node), struct my_rb_node, rb_entry)->key);    \
    } else {    \
        printf(name ": nil\n"); \
    }   \
} while (0)

static void __rb_desplay_node(struct my_rb_node *pos)
{
    printf("self: (%s), val: %d\n", 
        rb_is_node_black(&pos->rb_entry) ? "black" : "red", 
        pos->key);
    __RB_DESPLAY_A_SINGLE_NODE("brother", rb_brother(&pos->rb_entry));
    __RB_DESPLAY_A_SINGLE_NODE("parent", rb_parent(&pos->rb_entry));
    __RB_DESPLAY_A_SINGLE_NODE("uncle", rb_brother(rb_parent(&pos->rb_entry)));
    __RB_DESPLAY_A_SINGLE_NODE("grandparent", rb_parent(rb_parent(&pos->rb_entry)));
    __RB_DESPLAY_A_SINGLE_NODE("grand_grandparent", rb_parent(rb_parent(rb_parent(&pos->rb_entry))));
    __RB_DESPLAY_A_SINGLE_NODE("brother_of_grandparent", rb_brother(rb_parent(rb_parent(&pos->rb_entry))));
    __RB_DESPLAY_A_SINGLE_NODE("left", pos->rb_entry.left);
    __RB_DESPLAY_A_SINGLE_NODE("right", pos->rb_entry.right);
}


/// 测试红黑树中所有节点的合法性，合法返回0，非法返回1
static int __rb_is_all_nodes_valid(struct rb_root *root)
{
    if (root == NULL 
        || root->opts == NULL 
        || root->opts->keys_cmp_fun == NULL 
        || root->opts->get_key_fun == NULL
    ) {
        /// root及root内的函数指针不能为空。
        return 1;
    }
    if (root->node == NULL) {
        /// 空树合法。
        return 0;
    }
    
    int ret;
    int cnt = 0;
    struct my_rb_node *pos;
    struct my_rb_node *n;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        /// 遍历红黑树，并检查所有节点的合法性。
        ret = __rb_is_node_valid(&pos->rb_entry);
        if (ret != 0) {
            /// 遍历到了一个不合法的节点。
            printf("cnt: %d:\n", cnt);
            __rb_show_subtree_list(pos, 1);
            return ret;
        }
        cnt++;
    }

    int black_depth = __rb_check_black_balance(root->node);
    if (black_depth < 0) {
        /// 红黑树不满足黑平衡。
        return 1;
    }
    return 0;
}


/// 复用二叉树的测试代码
static void rbtree_basic_test(void)
{
    int test_nums[] = {
        487, 373, 498, 73, 310, 218, 151, 427, 109, 131, 162, 41, 494, 349, 246, 261, 
        124, 271, 367, 346, 358, 78, 114, 238, 103, 465, 77, 442, 470, 415, 304, 47, 
        217, 146, 52, 326, 140, 127, 356, 255, 216, 365, 5, 148, 7, 391, 280, 296, 
        321, 249, 159, 332, 210, 177, 40, 27, 118, 200, 107, 71, 58, 100, 195, 239, 
        496, 135, 93, 88, 37, 181, 254, 433, 95, 402, 51, 495, 198, 418, 458, 492, 
        323, 112, 207, 123, 430, 397, 139, 383, 499, 269, 104, 89, 337, 192, 406, 128, 
        267, 306, 407, 265, 315, 259, 257, 170, 82, 245, 437, 416, 447, 446, 115, 14, 
        504, 316, 486, 475, 57, 48, 178, 439, 436, 3, 136, 183, 270, 376, 472, 307, 
        147, 282, 43, 425, 491, 90, 116, 264, 250, 353, 500, 394, 175, 482, 154, 287, 
        318, 237, 196, 66, 400, 324, 330, 384, 45, 262, 171, 110, 67, 168, 419, 226, 
        453, 412, 248, 1, 79, 179, 158, 393, 19, 344, 225, 241, 202, 240, 194, 176, 
        190, 102, 399, 456, 11, 341, 411, 371, 44, 336, 133, 54, 372, 342, 281, 91, 
        279, 83, 357, 347, 405, 230, 39, 23, 388, 169, 343, 22, 205, 18, 50, 59, 
        182, 235, 335, 480, 284, 464, 334, 30, 273, 403, 288, 443, 355, 64, 130, 143, 
        477, 413, 423, 440, 505, 199, 460, 485, 422, 468, 144, 0, 150, 62, 268, 243,
        408, 187, 309, 351, 55, 36, 375, 212, 32, 108, 166, 96, 305, 211, 184, 15, 
        493, 450, 377, 466, 484, 60, 6, 333, 111, 325, 173, 87, 165, 380, 509, 160, 
        289, 191, 322, 503, 186, 473, 295, 74, 379, 152, 424, 26, 258, 25, 328, 382, 
        219, 502, 511, 149, 260, 327, 278, 92, 448, 478, 63, 389, 506, 4, 285, 206, 
        8, 469, 97, 489, 209, 33, 242, 508, 350, 99, 300, 94, 435, 34, 20, 445, 
        13, 291, 362, 283, 156, 134, 2, 331, 421, 463, 348, 203, 98, 381, 231, 308, 
        174, 204, 317, 299, 396, 247, 387, 137, 234, 53, 28, 361, 228, 180, 121, 189, 
        302, 428, 501, 474, 320, 76, 368, 451, 398, 185, 197, 444, 223, 125, 481, 233, 
        488, 120, 461, 420, 386, 17, 314, 70, 142, 429, 244, 301, 274, 65, 276, 449, 
        312, 220, 303, 201, 378, 49, 370, 455, 272, 42, 510, 29, 352, 286, 297, 164, 
        208, 72, 275, 459, 479, 215, 311, 31, 126, 81, 10, 188, 263, 364, 21, 354, 
        229, 232, 457, 141, 462, 9, 153, 80, 119, 56, 369, 476, 213, 172, 222, 497, 
        417, 224, 84, 266, 68, 157, 360, 434, 294, 227, 483, 431, 163, 161, 507, 69, 
        85, 329, 392, 292, 319, 167, 390, 35, 101, 38, 414, 155, 438, 113, 395, 253, 
        122, 401, 441, 290, 454, 338, 339, 490, 298, 404, 313, 471, 363, 105, 24, 214, 
        193, 340, 221, 467, 256, 251, 409, 410, 117, 145, 75, 432, 252, 345, 366, 452, 
        132, 236, 61, 46, 129, 426, 277, 86, 16, 106, 293, 359, 138, 374, 12, 385,
    };
    // static int test_nums[16777216];
    int ret = 0;
    int cnt = 0;
    int current = 0;
    size_t test_nums_len = sizeof(test_nums) / sizeof(int);
    struct rb_root *root = CREATE_RB_TREE();
    struct my_rb_node *pos = NULL;
    struct my_rb_node *n = NULL;

    // /// 初始化并打乱数组。
    // for (int i = 0; i < test_nums_len; i++) {
    //     test_nums[i] = i;
    // }
    // for (int i = 0; i < test_nums_len; i++) {
    //     int pos1 = rand() % test_nums_len;
    //     int pos2 = rand() % test_nums_len;
    //     int __tmp_num = test_nums[pos1];
    //     test_nums[pos1] = test_nums[pos2];
    //     test_nums[pos2] = __tmp_num;
    // }
    
    /// 将所有元素插入二叉树。
    for (cnt = 0; cnt < test_nums_len; cnt++) {
        struct my_rb_node *new_node = CREATE_RB_NODE(test_nums[cnt]);
        if (new_node == NULL) {
            LOG_TEST_FAIL("failed to create new node! ");
            printf("cnt: %d, num: %d\n", cnt, test_nums[cnt]);
            break;
        }
        if (rb_insert_color(root, &new_node->rb_entry) != &new_node->rb_entry) {
            LOG_TEST_FAIL("failed to insert new node! ");
            printf("cnt: %d, num: %d\n", cnt, test_nums[cnt]);
            break;
        }
        // ret = __rb_is_all_nodes_valid(root);
        // if (ret != 0) {
        //     LOG_TEST_FAIL("rbtree is not fully valid!\n");
        //     printf("cnt: %d, num: %d\n", cnt, test_nums[cnt]);
        //     break;
        // }
    }
    
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("rb nodes are all created!\n");
    }
    
    /// 测试整棵树的合法性
    ret = __rb_is_all_nodes_valid(root);
    if (ret != 0) {
        LOG_TEST_FAIL("rbtree is not fully valid!\n");
    } else {
        LOG_TEST_PASS("rbtree is fully valid!\n");
    }


    /// 测试顺序遍历
    cnt = 0;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != cnt) {
            LOG_TEST_FAIL("current: %d, cnt: %d\n", current, cnt);
            break;
        }
        cnt++;
    }
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("for each rb_node test succeed!\n");
    }

    /// 测试逆序遍历
    cnt = test_nums_len - 1;
    rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != cnt) {
            LOG_TEST_FAIL("current: %d, cnt: %d\n", current, cnt);
            break;
        }
        cnt--;
    }
    if (cnt == -1) {
        LOG_TEST_PASS("for each rb_node(inv) test succeed!\n");
    }

    /// 查找测试
    for (cnt = 0; cnt < test_nums_len; cnt++) {
        struct rb_node *new_node = rb_find_key(root, (unsigned long)&cnt);
        current = *(int*)(rb_get_node_key(root, new_node));
        if (new_node == NULL) {
            LOG_TEST_FAIL("failed to create new node! ");
            printf("cnt: %d\n", cnt);
            break;
        }
        if (current != cnt) {
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, current: %d\n", cnt, current);
            break;
        }
    }
    
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("rb nodes search test succeed!\n");
    }

    /// 删除树中所有的奇数，并测试
    for (cnt = 1; cnt < test_nums_len; cnt += 2) {
        // printf("cnt: %d\n", cnt);
        struct rb_node *delete_node = rb_delete_color(root, (unsigned long)&cnt);
        if (delete_node == NULL) {
            LOG_TEST_FAIL("failed to delete node: ");
            printf("cnt: %d\n", cnt);
            break;
        }
        current = *(int*)(rb_get_node_key(root, delete_node));
        if (current != cnt) {
            LOG_TEST_FAIL("delete the wrong node: ");
            printf("cnt: %d， num: %d\n", cnt, current);
            break;
        }
        DESTROY_RB_NODE_BY_ENTRY(delete_node);
        // ret = __rb_is_all_nodes_valid(root);
        // if (ret != 0) {
        //     LOG_TEST_FAIL("rbtree is not fully valid!\n");
        //     printf("cnt: %d, num: %d\n", cnt, test_nums[cnt]);
        //     break;
        // }
    }
    if (cnt == test_nums_len + 1) {
        LOG_TEST_PASS("all deleted!\n");
    }

    /// 测试整棵树的合法性
    ret = __rb_is_all_nodes_valid(root);
    if (ret != 0) {
        LOG_TEST_FAIL("rbtree is not fully valid!\n");
    } else {
        LOG_TEST_PASS("rbtree is fully valid!\n");
    }

    // cnt = 0;
    // rb_foreach_entry_safe(root, pos, n, rb_entry) {
    //     current = pos->key;
    //     printf("%d, ", current);
    //     cnt += 2;
    // }
    // printf("\n");
    // cnt = test_nums_len - 2;
    // rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
    //     current = pos->key;
    //     printf("%d, ", current);
    //     cnt -= 2;
    // }
    // printf("\n");

    /// 测试顺序遍历
    cnt = 0;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != cnt) {
            LOG_TEST_FAIL("current: %d, cnt: %d\n", current, cnt);
            break;
        }
        cnt += 2;
    }
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("for each rb_node test succeed!\n");
    }

    /// 测试逆序遍历
    cnt = test_nums_len - 2;
    rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != cnt) {
            LOG_TEST_FAIL("current: %d, cnt: %d\n", current, cnt);
            break;
        }
        cnt -= 2;
    }
    if (cnt == -2) {
        LOG_TEST_PASS("for each rb_node(inv) test succeed!\n");
    }

    /// 查找测试
    for (cnt = 0; cnt < test_nums_len; cnt += 2) {
        struct rb_node *new_node = rb_find_key(root, (unsigned long)&cnt);
        current = *(int*)(rb_get_node_key(root, new_node));
        if (new_node == NULL) {
            LOG_TEST_FAIL("failed to create new node! ");
            printf("cnt: %d\n", cnt);
            break;
        }
        if (current != cnt) {
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, current: %d\n", cnt, current);
            break;
        }
    }
    
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("rb nodes search test succeed!\n");
    }

    /// 针对已经被删除元素的查找测试
    for (cnt = 1; cnt < (test_nums_len * 4); cnt += 2) {
        struct rb_node *new_node = rb_find_key(root, (unsigned long)&cnt);
        if (new_node != NULL) {
            current = *(int*)(rb_get_node_key(root, new_node));
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, current: %d\n", cnt, current);
            break;
        }
    }
    
    if (cnt == (test_nums_len * 4) + 1) {
        LOG_TEST_PASS("rb nodes search test succeed!\n");
    }

    /// 针对已经被删除元素的重复删除测试
    for (cnt = 1; cnt < (test_nums_len * 4); cnt += 2) {
        struct rb_node *new_node = rb_delete_color(root, (unsigned long)&cnt);
        if (new_node != NULL) {
            current = *(int*)(rb_get_node_key(root, new_node));
            LOG_TEST_FAIL("delete a node that is not existed! ");
            printf("cnt: %d, current: %d\n", cnt, current);
            break;
        }
    }
    
    if (cnt == (test_nums_len * 4) + 1) {
        LOG_TEST_PASS("rb nodes delete(no exist) test succeed!\n");
    }

    /// 针对已经被存在元素的重复插入测试
    struct my_rb_node *new_node = CREATE_RB_NODE(0);
    for (cnt = 0; cnt < (test_nums_len * 4); cnt += 2) {
        if (&new_node->rb_entry == rb_insert_color(root, &new_node->rb_entry)) {
            LOG_TEST_FAIL("insert a node that is already existed! ");
            printf("cnt: %d\n", cnt);
            break;
        }
    }
    DESTROY_RB_NODE(new_node);
    
    if (cnt == (test_nums_len * 4) + 2) {
        LOG_TEST_PASS("rb nodes insert(already exist) test succeed!\n");
    }

    DESTROY_RB_TREE(root);
}


void rbtree_simple_test(void)
{
    printf("\n* rbtree_simple_test:\n");
    rbtree_basic_test();
}
